use std::collections::VecDeque;
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    mut end: (usize, usize),
) -> Vec<(usize, usize)> {
    for row in &maze {
        println!("{:?}", row);
    }
    let mut queue = VecDeque::from([start]);
    let mut visited = Vec::new();
    let mut back = Vec::new();
    while let Some(current) = queue.pop_front() {
        if visited.contains(&current) {
            continue;
        }
        visited.push(current);
        let next: Vec<_> = [(-1, 0), (1, 0), (0, -1), (0, 1)]
            .into_iter()
            .filter_map(|(y, x)| {
                let y = current.0.checked_add_signed(y)?;
                let x = current.1.checked_add_signed(x)?;
                (*maze.get(y)?.get(x)? != '#').then_some((y, x))
            })
            .collect();
        queue.extend(next.iter().copied());
        back.extend(
            next.into_iter()
                .filter_map(|next| (!visited.contains(&next)).then_some((next, current))),
        );
    }
    dbg!(&back);
    let mut path = vec![end];
    for _ in 0..100 {
        if let Some(to) = back
            .iter()
            .find_map(|(from, to)| (*from == end).then_some(to))
        {
            path.push(*to);
            end = *to;
        } else if end == start {
            break;
        } else {
            return Vec::new();
        }
    }
    path.reverse();
    path
}
